home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2001 May / SGI Freeware 2001 May - Disc 1.iso / dist / fw_qt.idb / usr / freeware / include / qtl.h.z / qtl.h
C/C++ Source or Header  |  2001-04-12  |  6KB  |  224 lines
  1. /****************************************************************************
  2. ** $Id: qt/src/tools/qtl.h   2.3.0   edited 2001-01-26 $
  3. **
  4. ** Definition of Qt template library classes
  5. **
  6. ** Created : 990128
  7. **
  8. ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
  9. **
  10. ** This file is part of the tools module of the Qt GUI Toolkit.
  11. **
  12. ** This file may be distributed under the terms of the Q Public License
  13. ** as defined by Trolltech AS of Norway and appearing in the file
  14. ** LICENSE.QPL included in the packaging of this file.
  15. **
  16. ** This file may be distributed and/or modified under the terms of the
  17. ** GNU General Public License version 2 as published by the Free Software
  18. ** Foundation and appearing in the file LICENSE.GPL included in the
  19. ** packaging of this file.
  20. **
  21. ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
  22. ** licenses may use this file in accordance with the Qt Commercial License
  23. ** Agreement provided with the Software.
  24. **
  25. ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  26. ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27. **
  28. ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
  29. **   information about Qt Commercial License Agreements.
  30. ** See http://www.trolltech.com/qpl/ for QPL licensing information.
  31. ** See http://www.trolltech.com/gpl/ for GPL licensing information.
  32. **
  33. ** Contact info@trolltech.com if any conditions of this licensing are
  34. ** not clear to you.
  35. **
  36. **********************************************************************/
  37. #ifndef QTL_H
  38. #define QTL_H
  39.  
  40. #ifndef QT_H
  41. #include "qtextstream.h"
  42. #include "qstring.h"
  43. #endif // QT_H
  44.  
  45. #ifndef QT_NO_TEXTSTREAM
  46. template <class T>
  47. class QTextOStreamIterator
  48. {
  49. protected:
  50.     QTextOStream& stream;
  51.     QString separator;
  52.  
  53. public:
  54.     QTextOStreamIterator( QTextOStream& s) : stream( s ) {}
  55.     QTextOStreamIterator( QTextOStream& s, const QString& sep )
  56.     : stream( s ), separator( sep )  {}
  57.     QTextOStreamIterator<T>& operator= ( const T& x ) {
  58.     stream << x;
  59.     if ( !separator.isEmpty() )
  60.         stream << separator;
  61.     return *this;
  62.     }
  63.     QTextOStreamIterator<T>& operator*() { return *this; }
  64.     QTextOStreamIterator<T>& operator++() { return *this; }
  65.     QTextOStreamIterator<T>& operator++(int) { return *this; }
  66. };
  67. #endif //QT_NO_TEXTSTREAM
  68.  
  69. template <class InputIterator, class OutputIterator>
  70. inline OutputIterator qCopy( InputIterator _begin, InputIterator _end,
  71.                  OutputIterator _dest )
  72. {
  73.     while( _begin != _end )
  74.     *_dest++ = *_begin++;
  75.     return _dest;
  76. }
  77.  
  78.  
  79. template <class T>
  80. inline void qSwap( T& _value1, T& _value2 )
  81. {
  82.     T tmp = _value1;
  83.     _value1 = _value2;
  84.     _value2 = tmp;
  85. }
  86.  
  87.  
  88. template <class InputIterator>
  89. inline void qBubbleSort( InputIterator b, InputIterator e )
  90. {
  91.     // Goto last element;
  92.     InputIterator last = e;
  93.     --last;
  94.     // only one element or no elements ?
  95.     if ( last == b )
  96.     return;
  97.  
  98.     // So we have at least two elements in here
  99.     while( b != last ) {
  100.     bool swapped = FALSE;
  101.     InputIterator swap_pos = b;
  102.     InputIterator x = e;
  103.     InputIterator y = x;
  104.     y--;
  105.     do {
  106.         --x;
  107.         --y;
  108.         if ( *x < *y ) {
  109.         swapped = TRUE;
  110.         qSwap( *x, *y );
  111.         swap_pos = y;
  112.         }
  113.     } while( y != b );
  114.     if ( !swapped )
  115.         return;
  116.     b = swap_pos;
  117.     b++;
  118.     }
  119. }
  120.  
  121.  
  122. template <class Container>
  123. inline void qBubbleSort( Container &c )
  124. {
  125.   qBubbleSort( c.begin(), c.end() );
  126. }
  127.  
  128.  
  129. template <class Value>
  130. inline void qHeapSortPushDown( Value* heap, int first, int last )
  131. {
  132.     int r = first;
  133.     while( r <= last/2 ) {
  134.     // Node r has only one child ?
  135.     if ( last == 2*r ) {
  136.         // Need for swapping ?
  137.         if ( heap[r] > heap[ 2*r ] )
  138.         qSwap( heap[r], heap[ 2*r ] );
  139.         // That's it ...
  140.         r = last;
  141.     } else { // Node has two children
  142.         if ( heap[r] > heap[ 2*r ] && heap[ 2*r ] <= heap[ 2*r+1 ] ) {
  143.         // Swap with left child
  144.         qSwap( heap[r], heap[ 2*r ] );
  145.         r *= 2;
  146.         } else if ( heap[r] > heap[ 2*r+1 ] &&
  147.             heap[ 2*r+1 ] < heap[ 2*r ] ) {
  148.         // Swap with right child
  149.         qSwap( heap[r], heap[ 2*r+1 ] );
  150.         r = 2*r+1;
  151.         } else {
  152.         // We are done
  153.         r = last;
  154.         }
  155.     }
  156.     }
  157. }
  158.  
  159.  
  160. template <class InputIterator, class Value>
  161. inline void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n )
  162. {
  163.     // Create the heap
  164.     InputIterator insert = b;
  165.     Value* realheap = new Value[ n ];
  166.     // Wow, what a fake. But I want the heap to be indexed as 1...n
  167.     Value* heap = realheap - 1;
  168.     int size = 0;
  169.     for( ; insert != e; ++insert ) {
  170.     heap[++size] = *insert;
  171.     int i = size;
  172.     while( i > 1 && heap[i] < heap[ i / 2 ] ) {
  173.         qSwap( heap[i], heap[ i / 2 ] );
  174.         i /= 2;
  175.     }
  176.     }
  177.  
  178.     // Now do the sorting
  179.     for( uint i = n; i > 0; i-- ) {
  180.     *b++ = heap[1];
  181.     if ( i > 1 ) {
  182.         heap[1] = heap[i];
  183.         qHeapSortPushDown( heap, 1, (int)i - 1 );
  184.     }
  185.     }
  186.  
  187.     delete[] realheap;
  188. }
  189.  
  190.  
  191. template <class InputIterator>
  192. inline void qHeapSort( InputIterator b, InputIterator e )
  193. {
  194.     // Empty ?
  195.     if ( b == e )
  196.     return;
  197.  
  198.     // How many entries have to be sorted ?
  199.     InputIterator it = b;
  200.     uint n = 0;
  201.     while ( it != e ) {
  202.     ++n;
  203.     ++it;
  204.     }
  205.  
  206.     // The second last parameter is a hack to retrieve the value type
  207.     // Do the real sorting here
  208.     qHeapSortHelper( b, e, *b, n );
  209. }
  210.  
  211.  
  212. template <class Container>
  213. inline void qHeapSort( Container &c )
  214. {
  215.     if ( c.isEmpty() )
  216.     return;
  217.  
  218.     // The second last parameter is a hack to retrieve the value type
  219.     // Do the real sorting here
  220.     qHeapSortHelper( c.begin(), c.end(), *(c.begin()), c.count() );
  221. }
  222.  
  223. #endif
  224.